/*
 * Titulo: OrdenamientosInternos.java
 * Autor: Diego Serafin Martínez García, Oswaldo Ceballos Zavala (Inu)
 * Descripcion: Algoritmos de ordanamiento interno para los resultados
 * de la prueba enlace a nivel local (YUCATAN)
 
 * Universidad Autonoma de Yucatan
 * 
 */
package util;

import java.util.ArrayList;
import modelo.Escuela;

/**
 *
 * @author Diego
 */
//Modificar todos para ArrayList
public class OrdenamientosInternos {

    
    
    //Constantes de clase
    public static final int BURBUJA = 0;
    public static final int INSERCION = 1;
    public static final int SHELLSORT = 2;
    public static final int MERGESORT = 3;
    public static final int QUICKSORT = 4;
    
    /**
     * 
     * @param escuelas 
     */
    public void insercion(ArrayList<Escuela> escuelas) {
        int i, j;
        for (i = 1; i < escuelas.size(); i++) {
            for (j = i; j > 0 && escuelas.get(j).compareTo(escuelas.get(j - 1)); j--) {
                //intercambiar escuelas[j] y escuelas[j-1]

                Escuela tmp = escuelas.get(j);
                escuelas.set(j, escuelas.get(j - 1));
                escuelas.set(j - 1, tmp);

            }
        }
    } //fin insercion

    /**
     * 
     * @param escuelas 
     */
    public void burbuja(ArrayList<Escuela> escuelas) {
        int i, j;
        for (i = 0; i < escuelas.size() - 1; i++) {
            for (j = 0; j < escuelas.size() - 1 - i; j++) {
                if (escuelas.get(j + 1).compareTo(escuelas.get(j))) {
                    //intercambiar escuelas[j] y escuelas[j+1]
                    Escuela tmp = escuelas.get(j);
                    escuelas.set(j, escuelas.get(j + 1));
                    escuelas.set(j + 1, tmp);
                }
            }
        }
    } //fin burbujaMayor    

    /**
     * 
     * @param escuelas 
     */
    public void shellSort(ArrayList<Escuela> escuelas) {

        int interval, i;
        boolean band;

        interval = escuelas.size() + 1;

        while (interval > 1) {
            interval /= 2;
            band = true;

            while (band == true) {
                i = 0;
                band = false;
                while (i + interval < escuelas.size()) {

                    if (escuelas.get(i + interval).compareTo(escuelas.get(i))) {

                        Escuela aux = escuelas.get(i);
                        escuelas.set(i, escuelas.get(i + interval));
                        escuelas.set(i + interval, aux);

                        band = true;

                    }
                    i++;
                }
            }
        }  //fin while
    } //fin metodo shellSort    

    /**
     * 
     * @param L1
     * @param L2
     * @return 
     */
    private ArrayList<Escuela> mezcla(ArrayList<Escuela> L1, ArrayList<Escuela> L2) {

        ArrayList<Escuela> Lista = new ArrayList<Escuela>();
        //  int nL1 = 0, nL2 = 0;

        while (!L1.isEmpty() && !L2.isEmpty()) {

            if (L1.get(0).getPromedioGeneral() < L2.get(0).getPromedioGeneral()) {
                //Si elemento L1 es menor que el de L2
                Lista.add(L1.get(0));
                L1.remove(0);
                //Solo L2 tiene Elementos
                if (L1.isEmpty()) {
                    Lista.addAll(L2);
                    L2.clear();

                }
            } else {
                //Si elemento L2 es menor que el de L1

                Lista.add(L2.get(0));
                L2.remove(0);
                //Solo L1 Tiene Elementos
                if (L2.isEmpty() == true) {
                    Lista.addAll(L1);
                    L1.clear();

                }


            }


        } //fin while

        return Lista;
    } // fin mezcla

    /**
     *
     * @param L
     * @return
     */
    public ArrayList<Escuela> mergeSort(ArrayList<Escuela> L) {

        int n = L.size(), i, m;
        ArrayList<Escuela> L1 = new ArrayList<Escuela>(), L2 = new ArrayList<Escuela>();

        if (n > 1) {
            m = n / 2;
            for (i = 0; i < m; i++) {
                L1.add(L.get(i));
            }
            for (i = m; i < n; i++) {
                L2.add(L.get(i));
            }

            L = mezcla(mergeSort(L1), mergeSort(L2));


        }

        return L;

    } //fin mergeSort

    
    public ArrayList<Escuela> quicksort(ArrayList a) {
        return quicksort(a, 0, a.size() - 1);
    }

    //definicion recursiva

    /**
     * 
     * @param a
     * @param primero
     * @param ultimo
     * @return 
     */
    private ArrayList<Escuela> quicksort(ArrayList a, int primero, int ultimo) {
        int i, j, central;
        Escuela pivote;
        central = (primero + ultimo) / 2;
        pivote = (Escuela) a.get(central);
        i = primero;
        j = ultimo;
        Escuela aux;

        do {
            while (((Escuela) a.get(i)).getPromedioGeneral() < pivote.getPromedioGeneral()) {
                i++;
            }
            while (((Escuela) a.get(j)).getPromedioGeneral() > pivote.getPromedioGeneral()) {
                j--;
            }
            if (i <= j) {
                aux = (Escuela) a.get(i);
                a.set(i, (Escuela) a.get(j));
                a.set(j, aux);
                i++;
                j--;
            }
        } while (i <= j);
        if (primero < j) {
            quicksort(a, primero, j);
        }
        if (i < ultimo) {
            quicksort(a, i, ultimo);
        }
        return a;
    }//fin de quicksort 
    
    
} //fin clase OrdenamientosInternos
